旋转链表

发表于 | 分类于 |
字数统计: 694 字 | 阅读时长 ≈ 3 分钟

题目描述：给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。

示例 1：
img
输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

示例 2：
img
输入：head = [0,1,2], k = 4
输出：[2,0,1]

方法一：闭合为环

根据题意，我们可以假设链表是：1 -> 2 -> 3 -> 4 -> 5，移动位是 k，我们分析如下：

  • k < 5 的情况：实际移动的位数，就是 k 本身。

  • k > 5 的情况：

    • k 是 5 的整数倍：链表不会发生位置变化。

    • k 不是 5 的整数倍：实际移动位数是 k%5 的值。

知道了上述的分析，我们很容易就能理清思路，流程如下：

  1. 计算链表的长度
  2. 链表最后一位值的 next 指向原链表首位数字，形成闭环，如下所示：
1
2
3
4
5
6
7
8
// 环图
1 -> 2 -> 3 -> 4 -> 5
↑                  ↓
↑                  ↓
 ←  ←  ←  ←  ←  ←   

// 线性图
1 -> 2 -> 3 -> 4 -> 5 -> 1 -> 2 -> 3 -> 4 -> 5 -> 1 -> 2 -> 3 -> 4 -> 5 -> ....
  1. 创建一个变量，接收从 k 处截断后的链表，假设 k = 2，我们就会从 3 这里处截断，然后 3 的 next 指向 null 即可，所以该变量的值是 4 -> 5 -> 1 -> 2 -> 3 -> null。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
  public ListNode rotateRight(ListNode head, int k) {
    // 1. 特判
    if(k == 0 || head == null || head.next == null){
      return head;
    }

    // 2. 计算出原链表的长度为n
    int n = 1;
    ListNode iter = head;
    while(iter.next != null){
      iter = iter.next;
      // 此时n记录的是链表的末尾节点
      n++;                                
    }

    // 3. 找到移动k位后新链表的最后一个节点
    int add = n - k % n;                    		// add 记录的是新链表的最后一个节点
    if(add == n){                           			// 如果k 刚好为n的整数倍数，新链表将于原链表相同
      // 直接返回原链表即可
      return head;                        
    }

    // 4. 处理逻辑
    iter.next = head;                       		// 将当前链表闭合为环
    while(add-- > 0){                       			// 将iter指向新链表的最后一个节点位置
      iter = iter.next;   
    }
    ListNode ret = iter.next;               		// 此时 ret为移动k位后新链表的头
    iter.next = null;                       		// 将环断开
    return ret;                             		// 返回新链表
  }
}

复杂度分析

  • 时间复杂度：O(n)，最坏情况下，我们需要遍历该链表两次。
  • 空间复杂度：O(1)，我们只需要常数的空间存储若干变量。

执行结果：通过

  • 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户

  • 内存消耗：37.7 MB, 在所有 Java 提交中击败了70.11%的用户